package gold.digger;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC1419 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int minNumberOfFrogs(String croakOfFrogs) {
            int length = croakOfFrogs.length();
            if (length % 5 != 0) {
                return -1;
            }
            int curSize = 0, maxSize = 0;
            int[] counts = new int[4];
            for (int i = 0; i < length; i++) {
                char c = croakOfFrogs.charAt(i);
                int index = getIndex(c);
                if (index == 0) {
                    counts[index]++;
                    curSize++;
                    maxSize = Math.max(maxSize, curSize);
                } else {
                    counts[index - 1]--;
                    if (counts[index - 1] < 0) {
                        return -1;
                    }
                    if (index < 4) {
                        counts[index]++;
                    } else {
                        curSize--;
                    }
                }
            }
            for (int i = 0; i < 4; i++) {
                if (counts[i] != 0) {
                    return -1;
                }
            }
            return maxSize;
        }

        public int getIndex(char c) {
            switch (c) {
                case 'c':
                    return 0;
                case 'r':
                    return 1;
                case 'o':
                    return 2;
                case 'a':
                    return 3;
                case 'k':
                    return 4;
                default:
                    return -1;
            }
        }
    }


    class Solution_Fail {
        public int minNumberOfFrogs(String croakOfFrogs) {
            Map<Character, List<Integer>> ckMap = new LinkedHashMap<>();
            ckMap.put('c', new ArrayList<>());
            ckMap.put('r', new ArrayList<>());
            ckMap.put('o', new ArrayList<>());
            ckMap.put('a', new ArrayList<>());
            ckMap.put('k', new ArrayList<>());

            for (int i = 0; i < croakOfFrogs.length(); i++) {
                char ch = croakOfFrogs.charAt(i);
                if (ckMap.containsKey(ch)) {
                    ckMap.get(ch).add(i);
                }
            }

            int ans = 0, prevIdx = -1, curLoopMinDis = Integer.MAX_VALUE, shortCnt = 0;
            boolean flag = true;
            while (flag) {
                for (Character ch : ckMap.keySet()) {
                    if (ckMap.get(ch).size() <= 0 || ckMap.get(ch).iterator().next() < prevIdx) {
                        flag = false;
                        break;
                    }
                    curLoopMinDis = Math.min(curLoopMinDis, ckMap.get(ch).size() >= 2 ? ckMap.get(ch).get(1) - ckMap.get(ch).get(0) : Integer.MAX_VALUE);
                    prevIdx = ckMap.get(ch).get(0);
                    ckMap.get(ch).remove(0);
                    if (ch == 'k') {
                        prevIdx = -1;
                        ans++;
                        if (curLoopMinDis == 5) shortCnt++;
                        curLoopMinDis = Integer.MAX_VALUE;
                    }
                }
            }

            if (ans * 5 != croakOfFrogs.length()) return -1;
            return ans - shortCnt;
        }
    }

    public void run() {
//        System.out.println(new Solution().minNumberOfFrogs("croakcroak"));
//        System.out.println(new Solution().minNumberOfFrogs("crcoakroak"));
//        System.out.println(new Solution().minNumberOfFrogs("croakcrook"));
        System.out.println(new Solution().minNumberOfFrogs("crocakcroraoakk"));
    }

    public static void main(String[] args) throws Exception {
        LC1419 an = new LC1419();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
